11001. Ожерелье

 

Люди из некоторого племени делают ожерелья из глины. Все кольца одного ожерелья имеют одинаковый диаметр. Толщина каждого кольца одинакова. Например, ниже представлено ожерелье из четырех колец:

Пусть V – первоначальный объем глины, из которой делается ожерелье, V0 – объем глины, теряемый в процессе выпекания. Диаметр D каждого кольца равен

D =

Если V £ V0, то ни одно кольцо не может быть сделано. Рассмотрим пример, в котором V = 10, V0 = 1. Если делать из глины одно кольцо, то его диаметр будет равен D = 0.3 = 0.9. При изготовлении двух колец глину следует разделить на две части, объем каждой из которых равен V / 2 = 5. Из каждого куска можно сделать кольцо диаметром D = 0.3 = 0.6. Диаметр всего ожерелья будет равен 0.6 * 2 = 1.2.

В задаче необходимо найти такое количество колец, при изготовлении которых ожерелье будет иметь максимальную длину.

 

Вход. Каждая строка состоит из двух чисел: V (0 < V £ 60000) и V0 (0 < V0 £ 600). Последний тест содержит V = V0 = 0 и не обрабатывается.

 

Выход. Для каждого теста вывести количество колец, при котором ожерелье будет иметь максимальную длину. Если ожерелье сделать невозможно, или искомое число колец определяется не однозначно, то вывести 0.

 

Пример входа

10 1

10 2

0 0

 

Пример выхода

5

0

 

 

РЕШЕНИЕ

математика

 

Анализ алгоритма

Пусть ожерелье будет самым длинным, если оно содержит n колец. Диаметр каждого кольца равен

D = 0.3 = 0.3

Длина всего ожерелья d равна

d = D * n = 0.3 = 0.3

Значение d будет максимальным, когда функция f(n) = Vn – V0n2 принимает наибольшее значение. Приравняем производную к 0: f’(n) = V – 2V0n = 0, откуда n = V / 2V0. Поскольку n является целым, то искомым n может быть как значение , так и . Вычисляем длину ожерелий при этих значениях n и находим наибольшую. Если длины одинаковы, то выводим 0 (число колец определяется не однозначно). Проверяем также возможность выпечки n колец из исходного количества глины: если V £ V0 * n, то сделать ожерелье невозможно.

 

Реализация алгоритма

Функция f вычисляет длину ожерелья, принимая на вход значения V, V0 и n.

 

double f(int v, int v0,int n)

{

  return 0.3 * sqrt(1.0 * v * n - v0 * n * n);

}

 

Основной цикл программы. Вводим значения V и V0, вычисляем значение n = . Проверяем возможность выпечки ожерелья для этого значения n. Вычисляем длину ожерелий для n =  и для n =  + 1, сравниваем и находим наибольшую из них. В случае равенства выводим 0.

 

while(scanf("%d %d",&v,&v0), v + v0 > 0)

{

  n = int(0.5 * v / v0);

  if (v <= v0 * n) {printf("0\n"); continue;}

  r1 = f(v,v0,n);

  r2 = f(v,v0,n+1);

  if (r2 > r1) n++;

  if (fabs(r1 - r2) < 1e-7) printf("0\n");

  else printf("%d\n",n);

}